﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using FCA.Dto;

namespace FCA.Algorithm {
    /// <summary>
    /// Base on the paper
    ///     A Fast algorithm for building the Hasse Diagram of a Galois Lattice
    ///     (Petko Valchev, Rokia Missaoui, Pierre Lebrun)
    /// Hasse algorithm to build the FCA galois
    /// </summary>
    public static class Hasse {
        public static Lattice BuildLattice(List<Concept> c) {
            Lattice l = new Lattice();

            Concept.Sort(c);
            l.AddConceptWithID(c[0]);

            List<Concept> border = new List<Concept>();
            border.Add(c[0]);

            int length = c.Count;
            for (int i = 1; i < length; i++) {
                HashSet<ItemSet> intents = new HashSet<ItemSet>();
                foreach (Concept c1 in border) {
                    intents.Add(c1.Items.IntersectWith(c[i].Items));
                }
                List<ItemSet> coverIntents = Hasse.Maxima(intents.ToList());
                foreach (ItemSet item in coverIntents) {
                    Concept c1 = FindConcept(item, l.Concepts);
                    MakeLink(c[i], c1);
                };
                RemoveUpperCover(border, c[i]);
                border.Add(c[i]);
                l.AddConceptWithID(c[i]);
            }
            return l;
        }

        private static void RemoveUpperCover(List<Concept> border, Concept concept) {
            for (int i = border.Count - 1; i >= 0; i--) {
                Concept c = border[i];
                if (concept.ParentID.Contains(c.ID)) {
                    border.RemoveAt(i);
                }
            }


        }

        #region MakeLink
        private static void MakeLink(Concept concept, Concept upperConcept) {
            upperConcept.AddChild(concept.ID);
            concept.AddParent(upperConcept.ID);
        }

        #endregion

        #region FindConcept
        public static Concept FindConcept(ItemSet y, Dictionary<int, Concept> concepts) {
            //get the first upper-conver of Y
            Concept c = new Concept();
            c = Generator(y, concepts);
            while (c != null && !c.Items.IsEqual(y)) {
                int index = 0;
                Concept c1 = NextUpperCover(c, concepts, ref index);
                while (c1 != null && !y.IsSubSetOf(c1.Items)) {
                    c1 = NextUpperCover(c, concepts, ref index);
                }
                if (c1 != null) {
                    c = c1;
                }
                else {
                    return c;
                }
            }
            return c;
        }

        /// <summary>
        /// Get element at index
        /// </summary>
        /// <param name="c"></param>
        /// <param name="concepts"></param>
        /// <param name="index"></param>
        /// <returns></returns>
        private static Concept NextUpperCover(Concept c, Dictionary<int, Concept> concepts, ref int index) {
            if (c.ParentID.Count > index) {
                int key = c.ParentID.ElementAt(index);
                index++;
                return concepts.ContainsKey(key) ? concepts[key] : null;
            }
            return null;
        }

        /// <summary>
        /// this method need to improve!
        /// </summary>
        /// <param name="y"></param>
        /// <param name="concepts"></param>
        /// <returns></returns>
        private static Concept Generator(ItemSet y, Dictionary<int, Concept> concepts) {
            foreach (KeyValuePair<int, Concept> item in concepts) {
                if (item.Value.Items.IsSuperSetOf(y)) {
                    return item.Value;

                }
            }
            return null;
        }
        #endregion

        #region Maxima
        public static List<ItemSet> Maxima(List<ItemSet> y) {
            List<ItemSet> maxi = new List<ItemSet>();
            ItemSet.Sort(y);
            foreach (ItemSet yi in y) {
                bool isMin = true;
                foreach (ItemSet ya in maxi) {
                    isMin = isMin && !ya.IsSuperSetOf(yi);
                }
                if (isMin) {
                    maxi.Add(yi);
                }
            }
            return maxi;
        }

        public static List<ItemSet> Maxima(List<ItemSet> y, int m) {
            List<ItemSet> maxi = new List<ItemSet>();
            y = ItemSet.Sort(y, m);
            foreach (ItemSet yi in y) {
                bool isMin = true;
                foreach (ItemSet ya in maxi) {
                    isMin = isMin && !ya.IsSuperSetOf(yi);
                }
                if (isMin) {
                    maxi.Add(yi);
                }
            }
            return maxi;
        }

        public static List<Concept> Maxima(List<Concept> y, int m) {
            List<Concept> maxi = new List<Concept>();
            y = Concept.Sort(y, m);
            foreach (Concept yi in y) {
                bool isMin = true;
                foreach (Concept ya in maxi) {
                    isMin = isMin && !ya.Items.IsSuperSetOf(yi.Items);
                }
                if (isMin) {
                    maxi.Add(yi);
                }
            }
            return maxi;
        }
        #endregion
    }
}